package com.example.link;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/3/5
 * @Created by Jonathan
 */
public class LinkedList {
    private static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

    }

    /**
     * 打印链表
     *
     * @param head 头结点
     */
    private static void print(Node head) {
        Node cur = head;
        while (cur != null) {
            System.out.printf("%d ", cur.value);
            cur = cur.next;
        }
        System.out.print("\n");
    }


    /**
     * 输入链表头结点 奇数长度返回中点 偶数长度返回上中点
     *
     * @param head 头结点
     * @return 中点或者上中点
     */
    public static Node midOrUpMidNode(Node head) {
        // 对应的是没有点 一个点 两个点的情况
        if (head == null || head.next == null || head.next.next == null)
            return head;
        // 链表至少有三个点
        // 创建快慢指针
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // todo  下面三个是练习
    /**
     * 输入链表头结点 奇数长度返回中点 偶数长度返回下中点
     *
     */


    /**
     * 输入链表头结点 奇数长度返回中点前一个  偶数长度返回上中点前一个
     *
     */

    /**
     * 输入链表头结点 奇数长度返回中点前一个  偶数长度返回下中点前一个
     *
     */


    /**
     * 逆序一个链表
     */

    public static Node reverse(Node head) {
        if (head == null || head.next == null)
            return head;
        // 说明至少有两个节点
        Node pre = head, cur = head.next, next = cur.next;
        // pre节点为尾节点 指向null
        pre.next = null;
        while (next != null) {
            // 改变指针指向
            cur.next = pre;
            pre = cur;
            cur = next;
            // 当next为null  说明cur是最后一个节点了 但是此时还没改变指向
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }

    public static Node reverseNNoRecur(Node head, int n) {
        // 说明最多只有一个节点
        if (head == null || head.next == null)
            return head;
        // 说明至少有两个节点
        Node pre = head, cur = head.next, next = cur.next, successor;
        // pre节点为尾节点 指向null
        pre.next = null;
        while (next != null) {
            // 改变指针指向
            cur.next = pre;
            pre = cur;
            cur = next;
            // 当next为null  说明cur是最后一个节点了 但是此时还没改变指向
            next = next.next;
            if (--n == 1) {
                successor = cur.next;
                break;
            }
        }
        cur.next = pre;
        return cur;
    }

    /**
     * 递归反转
     * 对于递归算法 最重要的就是明确定义递归函数的行为
     * 输入一个节点head，将“以head为起点”的链表反转，并返回“反转完成后的链表头结点”
     *
     * @return 头结点
     */
    public static Node reverse1(Node head) {
        // 头结点为null 或者 只有一个节点
        // 递归出口
        if (head == null || head.next == null)
            return head;
        // 这个是反转过后的头结点
        Node node = reverse1(head.next);
        // 这样就逆序过来
        head.next.next = head;
        // node代表的是新的头结点  原来的尾节点
        // 因此直接用node来操作确实不行！要用当前相对的来改变
        //node.next = head;// todo 这一句为什么不是这样呢?
        head.next = null;
        return node;
    }

    /**
     * 反转以head为起点的n个节点，返回新的头结点
     * 感觉这个还是有点抽象！多多练习
     *
     * @param head
     * @param n
     * @return
     */

    private static Node successor = null;


    public static Node reverseN(Node head, int n) {
        if (n == 1) {
            successor = head.next;
            // 这个就是头结点！！！
            return head;
        }
        Node last = reverseN(head.next, --n);
        head.next.next = head;
        head.next = successor;
        return last;
    }


    /**
     * 测试链表反转
     */

    @Test
    public void testReverse() {
        Node node1 = new Node(10);
        Node node2 = new Node(11);
        Node node3 = new Node(12);
        Node node4 = new Node(13);
        Node node5 = new Node(1100);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        print(node1);
        //print(reverseN(node1, 3));
        Node reverse = reverseNNoRecur(node1, 3);
        print(reverse);

    }

    /**
     * 给定一个单链表的头结点head 请判断该链表是否为回文结构
     * 笔试 用栈
     * 链表反转之后比较 比较之后再恢复
     */
    public static boolean isPalindrome1(Node head) {


        return true;
    }

    public static boolean isPalindrome2(Node head) {


        return true;
    }

    public static boolean isPalindrome3(Node head) {


        return true;
    }

    // 将单链表按某值划分成左边小 中间相等 右边大的形式
    // 1) 把链表放到数组里面，在数组上做partition(笔试)
    // 2) 分成小中大三部分 再把各部分串起来
    public static Node listPartition(Node head, int pivot) {
        Node lh = null, lt = null, mh = null, mt = null, hh = null, ht = null;
        Node cur = head;
        while (cur != null) {
            if (cur.value < pivot) {
                // 小于
                if (lh == null) {
                    lh = lt = cur;
                } else {
                    lt.next = cur;
                    lt = lt.next;
                }

            } else if (cur.value == pivot) {
                // 等于
                if (mh == null) {
                    mh = mt = cur;
                } else {
                    mt.next = cur;
                    mt = mt.next;
                }

            } else {
                // 大于
                if (null == hh) {
                    hh = ht = cur;
                } else {
                    ht.next = cur;
                    ht = ht.next;
                }
            }
            cur = cur.next;
        }
        // 小于等于大于区域到底有没有  还需要考虑一下！
        if (null != lt) {
            lt.next = mh;
            mt = mt == null ? lt : mt;
        }
        // 上面的if 不管跑了没有 mt all reconnect
        if (mt != null) {
            mt.next = hh;

        }
        //
        return lh != null ? lh : (mh != null ? mh : hh);
    }

    @Test
    public void testListPartition() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(2);
        list.add(-100);
        list.add(100);
        Node head = create(list);
        System.out.print("原来的链表为:");
        print(head);
        Node listPartition = listPartition(head, 20);
        System.out.print("ListPartition的链表为:");
        print(listPartition);
    }

    /**
     * 传进来list 创建链表
     *
     * @param list
     * @return
     */
    private static Node create(List<Integer> list) {
        Node head = new Node(list.get(0));
        Node cur = head;
        for (int i = 1; i < list.size(); i++) {
            cur.next = new Node(list.get(i));
            cur = cur.next;
        }
        return head;
    }

    @Test
    public void testCreate() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(2);
        list.add(-100);
        list.add(100);
        Node head = create(list);
        print(head);
        //Node listPartition = listPartition(head, 2);
        //print(listPartition);
    }

    // 常见面试题
    // 能不能不给单链表的头结点，只给想要删除的节点，就能做到在链表上把这个点删除?
    // 不能 有很多的问题
    // 借尸还魂


}
